package classic;

/**
 * 题目：一个二维数组中，每行按照从左到右数字递增，每列按照从上到下数字递增
 * 给定一个这样的数组和一个数字，求数字是否在数组中，例如：二维数组如下：
 * 1 3 4 18
 * 2 7 9 22
 * 5 11 24 30
 * 给定的数字为7，则返回true，给定数字为10，则返回false
 *
 * @author zj
 */
public class TwoDimensionalArray {
    public static void main(String[] args) {
        int[][] arr = {
                {1, 3, 4, 18},
                {2, 7, 9, 22},
                {5, 11, 24, 30}
        };
        System.out.println(inArrays(arr, 7));
        System.out.println(inArrays(arr, 10));
    }

    public static boolean inArrays(int[][] arr, int number) {
        //边界判断
        if (arr == null) {
            return false;
        }
        int rows = arr.length;
        if (rows == 0) {
            return false;
        }
        int columns = arr[0].length;
        if (columns == 0) {
            return false;
        }

        //从右上角的元素开始遍历，如果number比当前元素小，则只可能在元素左边，即j减一
        //如果number比当前元素大，则只能在元素下边，即i加一
        int i = 0;
        int j = columns - 1;
        while (i < rows && j >= 0) {
            if (arr[i][j] == number) {
                return true;
            } else if (arr[i][j] > number) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
}
